package algorithm.合并两个有序链表;


public class Solution {


    public LinkList mergeKLists(LinkList[] lists) {
        //初始化一个初始对比对象
        LinkList ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }


    public LinkList mergeTwoLists(LinkList a, LinkList b) {
        if (a == null || b == null) {
            //任意一个为空直接返回
            return a != null ? a : b;
        }
        //申明一个空的链表，用于存放合并结果
        LinkList head = new LinkList(0);
        //申明三个指针：结果链表、a、b
        LinkList tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        //a或者b里面可能还有剩下未对比的节点，直接讲这些节点追加到结果链表的末尾就行了
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}


/**
 * 链表节点
 */
class LinkList {
    /**
     * 节点值
     */
    public int val;
    public LinkList next;

    public LinkList(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public LinkList getNext() {
        return next;
    }

    public void setNext(LinkList next) {
        this.next = next;
    }
}

//        作者：LeetCode-Solution
//        链接：https://leetcode.cn/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。